#pragma once

#include<vector>
#include<map>

using namespace std;

template<class T>
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n,-1)
	{}

	void Union(size_t x1, size_t x2)
	{
		size_t root1 = FindRoot(x1);
		size_t root2 = FindRoot(x2);

		if (root1 == root2) return;

		if (_ufs[root1] > _ufs[root2])
			swap(root1, root2);

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	size_t FindRoot(size_t x)
	{
		size_t root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}

		while (_ufs[x] >= 0)
		{
			size_t parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}

		return root;
	}

	bool IsInset(size_t x1, size_t x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	size_t SetSize()
	{
		size_t res = 0;
		for (auto it : _ufs)
		{
			if (it < 0) res++;
		}
		return res;
	}

private:
	vector<T> _ufs;
};